package com.programmercarl.backtracking;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * https://leetcode.cn/problems/reconstruct-itinerary/
 * 重新安排行程
 *
 * @author yulongtian
 * @create 2025-01-14 10:29
 */
public class Test13 {
    public static void main(String[] args) {

    }

    List<String> res;
    List<String> path = new ArrayList<String>();

    public List<String> findItinerary(List<List<String>> tickets) {
        path.add("JFK");
        Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
        boolean[] used = new boolean[tickets.size()];
        backtrack((ArrayList) tickets, used);

        return res;
    }

    public boolean backtrack(ArrayList<List<String>> tickets, boolean[] used) {
        if (path.size() == tickets.size() + 1) {
            res = new ArrayList<>(path);
            return true;
        }

        for (int i = 0; i < tickets.size(); i++) {
            if (!used[i] && tickets.get(i).get(0).equals(path.get(path.size() - 1))) {
                used[i] = true;
                path.add(tickets.get(i).get(1));
                boolean backtrack = backtrack(tickets, used);
                if (backtrack) {
                    return true;
                }
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }

        return false;
    }

}
